package com.suanfa.sort;

/**
 * Created by buguniao on 16/2/14.
 */
public class Merge extends SuanFaTemplate {
    private static double[] arr1 ;

    public static void main(String[] args){
        Merge merge = new Merge();
        int size=200;
        double[] arr = merge.getRandomArray(size);
        StdDraw.setCanvasSize(1200,600);
        merge.draw(arr);
//        System.out.println("原始的数组："+Arrays.toString(arr));
        //是一个全为初始值的数组
        arr1 = new double[size];
        long timeCost = merge.run(arr);
//        System.out.println("排序后数组："+Arrays.toString(arr));
        System.out.println("timeCost="+timeCost);


    }

    @Override
    public long run(double[] arr) {
        long t1= System.currentTimeMillis();
        sort(arr,0,arr.length-1);
        long t2 =System.currentTimeMillis();
        return t2-t1;
    }
    public void sort(double[] arr,int lo,int hi){
        if(lo>=hi){
         return;
        }
        int mid = lo+(hi-lo)/2;
        //排序左边
        sort(arr,lo,mid);
        draw(arr);
        //排序右边
        sort(arr,mid+1,hi);
        draw(arr);
        //合并排序
        merge(arr,lo,mid,hi);
        draw(arr);
    }
    public void merge(double[] arr,int lo,int mid,int hi){
        int i=lo,j=mid+1;
        for(int k=lo;k<=hi;k++){
            arr1[k]=arr[k];
        }
        for(int k=lo;k<=hi;k++){
            if(i>mid){
                arr[k]=arr1[j++];
            }else if(j>hi){
                arr[k]=arr1[i++];
            }else if(less(arr1[j],arr1[i])){
                arr[k]=arr1[j++];
            }else{
                arr[k]=arr1[i++];
            }
        }
    }

    public void draw(double[] a){

        int n=a.length;
        StdDraw.clear();
        for(int i=0;i<n;i++){
            double x= 1.0*i/n;
            double y=a[i]/2.0;
            double rw=0.4/n;
            double rh=a[i]/2.0;
            StdDraw.filledRectangle(x,y,rw,rh);
        }
    }
}
